package com.data_structure_algorithm.data_structure.linked;

import java.util.Objects;
import java.util.Stack;

/**
 * @author 何章怀晓 hezhanghuaixiao
 * @version V1.0
 * @desc 链表翻转
 */
public class LinkedListFlip {

    static LinkedListNode headNode = new LinkedListNode(0);

    public static void main(String[] args) {
        LinkedListFlip linked = new LinkedListFlip();
        LinkedListNode linkedListNode = new LinkedListNode(1);
        linkedListNode.next = new LinkedListNode(3);
        linkedListNode.next.next = new LinkedListNode(5);


        LinkedListNode linkedListNode2 = new LinkedListNode(2);
        linkedListNode2.next = new LinkedListNode(4);
        linkedListNode2.next.next = new LinkedListNode(6);


        // linked.bianli(linkedListNode);
        System.out.println("反转");
        LinkedListNode hebing = linked.hb(linkedListNode, linkedListNode2);
        linked.bianli(hebing);


    }


    public LinkedListNode flip(LinkedListNode node) {


        LinkedListNode curr = node;//当前节点

        LinkedListNode next = null;//当前节点的下个节点

        LinkedListNode newNode = new LinkedListNode(0);//新链表

        while (curr != null) {
            next = curr.next;//当前节点的下个节点，用于下次遍历初始化

            //插队操作，将当前链表next节点变为当前节点的next
            curr.next = newNode.next;

            //将当前链表的后节点转为自己
            newNode.next = curr;

            //初始化下次循环
            curr = next;
        }

        //挂上


        return newNode.next;
    }

    public void add(LinkedListNode node) {

        LinkedListNode temp = headNode;

        boolean flag = false;

        while (true) {
            if (temp.next == null) {
                break;
            }

            if (temp.next.id == node.id) {//判重
                flag = true;
                break;
            }

            if (temp.next.id > node.id) {
                //变换位置

                break;
            }
            temp = temp.next;
        }

        if (flag) {
            System.out.println("重复数据不予添加...");
            return;
        }

        LinkedListNode next = temp.next;
        temp.next = node;
        node.next = next;
    }


    public void bianli(LinkedListNode linked) {
        if (linked == null) {
            return;
        }

        if (linked.next == null) {
            return;
        }

        LinkedListNode temp = linked;

        while (true) {
            if (temp == null) {
                break;
            }

            System.out.println(temp.toString());
            temp = temp.next;


        }
    }


    public void flipBinli(LinkedListNode linked) {
        LinkedListNode temp = linked;

        //遍历压栈
        Stack<LinkedListNode> stack = new Stack<>();

        while (temp.next != null) {
            stack.push(temp.next);

            temp = temp.next;
        }

        while (stack.size() > 0) {
            System.out.println(stack.pop().toString());

        }
    }


    public LinkedListNode mergeToLists(LinkedListNode l1, LinkedListNode l2) {
        //按照升序排列两个链表
        if (l1 == null) {
            //链表1为空,组合起来就是l2
            return l2;
        }
        if (l2 == null) {
            //链表2为空,组合起来就是l1
            return l1;
        }
        LinkedListNode cur1 = l1;
        LinkedListNode cur2 = l2;
        LinkedListNode NewHead = null;//新的链表存放合并好的链表
        LinkedListNode NewTail = null;//链表尾插需要遍历链表,找到链表末尾才能插入
        // 为了方便,用NewTail把链表末尾记录下来
        while (cur1 != null && cur2 != null) {
            if (cur1.id < cur2.id) {
                //那就将cur1插入到新链表末尾
                //需要考虑两种情况,新链表末尾NewTail是否为空
                if (NewTail == null) {//第一次进来
                    NewHead = cur1;
                    NewTail = cur1;
                } else {//不是首次进入
                    NewTail.next = cur1;
                    NewTail = NewTail.next;//更新NewTail的位置
                }
                cur1 = cur1.next;
            } else {
                //那就将cur2插入到新链表末尾
                //需要考虑两种情况,新链表末尾NewTail是否为空
                if (NewTail == null) {
                    NewHead = cur2;
                    NewTail = cur2;
                } else {
                    NewTail.next = cur2;
                    NewTail = NewTail.next;//更新NewTail的位置
                }
                cur2 = cur2.next;
            }
        }
        //当循环结束时,说明cur1和cur2有一个走到了末尾
        //把没走到末尾的剩下的链表都连在新链表末尾NewTail的后面
        if (cur1 == null) {
            NewTail.next = cur2;
        } else {
            NewTail.next = cur1;
        }
        return NewHead;
    }

    public LinkedListNode mg(LinkedListNode l1, LinkedListNode l2) {
        //
        if (l1 == null && l2 == null) {
            return null;
        }

        if (l1 == null) {
            return l2;
        }
        if (l2 == null) {
            return l1;
        }
        //创建对应temp指针
        LinkedListNode l1Temp = l1;
        LinkedListNode l2Temp = l2;

        //创建新链表,初始化均为null，尾节点的记录是为了避免重复遍历，每次直接追加即可
        LinkedListNode newLinkedHead = null;
        LinkedListNode newLinkedTail = null;

        while (l1Temp != null && l2Temp != null) {
            //开始
            if (l1Temp.id < l2Temp.id) {
                //两种情况
                //1.首次进入，头尾均为空
                if (newLinkedTail == null) {
                    //头尾均为此元素
                    newLinkedHead = l1Temp;
                    newLinkedTail = l1Temp;
                } else {
                    //不为空，不是首次进入,直接追加
                    newLinkedTail.next = l1Temp;
                    //后移尾巴
                    newLinkedTail = newLinkedTail.next;

                }
                //l1Temp后移
                l1Temp = l1Temp.next;

            } else {
                //两种情况
                //1.首次进入，头尾均为空
                if (newLinkedTail == null) {
                    //头尾均为此元素
                    newLinkedHead = l2Temp;
                    newLinkedTail = l2Temp;
                } else {
                    //不为空，不是首次进入,直接追加
                    newLinkedTail.next = l2Temp;
                    //后移尾巴
                    newLinkedTail = newLinkedTail.next;

                }
                l2Temp = l2Temp.next;


            }

            //如退出循环有以下几种情况
            //1.l1没了
            //将l2直接追加到l1后面
            if (l1Temp == null) {
                newLinkedTail.next = l2Temp;
                return newLinkedHead;
            }
            //2.l2没了

            if (l2Temp == null) {
                newLinkedTail.next = l1Temp;
                return newLinkedHead;
            }

        }
        //3.一起没了

        return newLinkedHead;


    }

    public LinkedListNode hebing(LinkedListNode l1, LinkedListNode l2) {
        //判空
        if (Objects.isNull(l1) && Objects.isNull(l2)) {
            return null;
        }

        if (Objects.isNull(l1)) {
            return l2;
        }

        if (Objects.isNull(l2)) {
            return l1;
        }

        //创建临时指针
        LinkedListNode l1Temp = l1;
        LinkedListNode l2Temp = l2;
        LinkedListNode newLinkedHead = null;
        LinkedListNode newLinkedTail = null;

        while (!Objects.isNull(l1Temp) && !Objects.isNull(l2Temp)) {

            //比大小
            if (l1Temp.id < l2Temp.id) {
                //是否首次进入
                if (Objects.isNull(newLinkedTail)) {
                    //首次
                    newLinkedHead = l1Temp;
                    newLinkedTail = l1Temp;
                } else {
                    //不是首次
                    newLinkedTail.next = l1Temp;
                    newLinkedTail = newLinkedTail.next;//尾指针添加新元素后后移，新节点为尾元素
                }

                //l1Temp后移
                l1Temp = l1Temp.next;


            } else {

                //是否首次进入
                if (Objects.isNull(newLinkedTail)) {
                    //首次
                    newLinkedHead = l2Temp;
                    newLinkedTail = l2Temp;
                } else {
                    //不是首次
                    newLinkedTail.next = l2Temp;
                    newLinkedTail = newLinkedTail.next;//尾指针添加新元素后后移，新节点为尾元素
                }

                //l1Temp后移
                l2Temp = l2Temp.next;


            }

        }

        //如l1没了
        if (Objects.isNull(l1Temp)) {
            newLinkedTail.next = l2Temp;
        }

        //如l2没了
        if (Objects.isNull(l2Temp)) {
            newLinkedTail.next = l1Temp;
        }

        return newLinkedHead;

    }

    public void flip2(LinkedListNode node) {
        //链表反向
        //思路，通过遍历实现，每次的点挂载新链表首节点位置


        //当前指针
        LinkedListNode cur = node;


        //next，代表当前节点的下一个节点
        LinkedListNode next = null;

        //定义新的链表
        LinkedListNode newLinked = new LinkedListNode(-1);

        while (!Objects.isNull(cur)) {
            next = cur.next;//获得当前节点的下节点

            //当前节点插队
            //当前节点的下节点为新链表的下一个节点
            cur.next = newLinked.next;

            //当前链表的下一个节点为当前节点
            newLinked.next = cur;


            //后移
            cur = next;
        }

        bianli(newLinked.next);


    }


    public void flip3(LinkedListNode node) {
        //创建新链表节点，每次遍历，将元素挂在新链表的最前端
        //没有头节点
        LinkedListNode newLinked = new LinkedListNode(-1);

        //临时指针
        LinkedListNode cur = node;

        LinkedListNode next = null;

        while (cur != null) {
            //获取当前节点的下一个节点，该节点是下次遍历的节点
            next = cur.next;
            //插队
            //将当前节点挂在新链表的最前端
            //新链表的next是当前节点的next
            cur.next = newLinked.next;
            //新链表的next是当前元素
            newLinked.next = cur;

            //初始化下轮遍历的cur
            cur = next;
        }

        bianli(newLinked.next);
    }


    public LinkedListNode hb(LinkedListNode l1, LinkedListNode l2) {
        if (l1 == null && l2 == null) return null;

        if (l1 == null) return l2;

        if (l2 == null) return l1;

        //定义temp指针
        LinkedListNode tempL1 = l1;
        LinkedListNode tempL2 = l2;

        //定义新链表
        LinkedListNode newLinkedHead = null;
        LinkedListNode newLinkedTail = null;

        while (tempL1 != null && tempL2 != null) {

            //判断两个链表的值
            //l1 > l2
            if (tempL1.id < tempL2.id) {
                //判断是否首次进来
                if (newLinkedHead == null) {
                    newLinkedHead = tempL1;
                    newLinkedTail = tempL1;

                } else {
                    newLinkedTail.next = tempL1;
                    newLinkedTail = newLinkedTail.next;
                }
                tempL1 = tempL1.next;


            }else {
                //判断是否首次进来
                if (newLinkedHead == null) {
                    newLinkedHead = tempL2;
                    newLinkedTail = tempL2;

                } else {
                    newLinkedTail.next = tempL2;
                    newLinkedTail = newLinkedTail.next;
                }
                tempL2 = tempL2.next;
            }


        }

        //一端没有数据了
        if (tempL1 == null) {
            newLinkedTail.next = tempL2;
        }

        if (tempL2 == null) {
            newLinkedTail.next = tempL1;
        }

        return newLinkedHead;


    }


}

class LinkedListNode {


    int id;
    LinkedListNode next;

    public LinkedListNode(int id) {
        this.id = id;
    }

    @Override
    public String toString() {
        return "LinkedListNode{" +
                "id=" + id +
                '}';
    }
}

